package 高级班;

import org.omg.CORBA.WStringValueHelper;

class Problem04_PalindromeMinCut {

    public static int minCut(String str) {
        if (str == null || str.equals("")) {
            return 0;
        }
        char[] chas = str.toCharArray();
        int len = chas.length;
        int[] dp = new int[len + 1];
        dp[len] = -1;
        boolean[][] p = new boolean[len][len];
        for (int i = len - 1; i >= 0; i--) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = i; j < len; j++) {
                if (chas[i] == chas[j] && (j - i < 2 || p[i + 1][j - 1])) {
                    p[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0];
    }

    //ytc
    public static int minCutytc(String str){
        if (str.length()==0||str.equals(""))
            return 0;
        boolean[][] valid=new boolean[str.length()][str.length()];
        for (int i=0;i<str.length();i++)
            valid[i][i]=true;
        for (int i=str.length()-2;i>=0;i--){
            for (int j=i+1;j<str.length();j++){
                if (j-i<2)
                    valid[i][j]=str.charAt(i)==str.charAt(j);
                else {
                    if (str.charAt(i)==str.charAt(j))
                        valid[i][j]=valid[i+1][j-1];
                }
            }
        }
        return process(0,str,valid);
    }
    public static int process(int start,String str,boolean[][] valid){
        if (valid[start][str.length()-1])
            return 0;
        if (start>=str.length()-1)
            return 0;
        int res=Integer.MAX_VALUE;
        for (int i=start;i<str.length();i++){
            if (valid[start][i])
                res=Math.min(res,1+process(i+1,str,valid));
        }
        return res;
    }

    //dp
    public static int minCutytc_dp(String str){
        if (str.length()==0||str.equals(""))
            return 0;
        boolean[][] valid=new boolean[str.length()][str.length()];
        for (int i=0;i<str.length();i++)
            valid[i][i]=true;
        for (int i=str.length()-2;i>=0;i--){
            for (int j=i+1;j<str.length();j++){
                if (j-i<2)
                    valid[i][j]=str.charAt(i)==str.charAt(j);
                else {
                    if (str.charAt(i)==str.charAt(j))
                        valid[i][j]=valid[i+1][j-1];
                }
            }
        }
        int[] dp=new int[str.length()];
        dp[str.length()-1]=0;
        for (int j=dp.length-2;j>=0;j--){
            if (valid[j][str.length()-1])
                dp[j]=0;
            else {
                int res = Integer.MAX_VALUE;
                for (int i = j; i < dp.length; i++) {

                    if (valid[j][i])
                        res = Math.min(res, 1 + dp[i]);
                }
                dp[j] = res;
            }
        }
        return dp[0];
    }

    // for test
    public static String getRandomStringOnlyAToD(int len) {
        int range = 'D' - 'A' + 1;
        char[] charArr = new char[(int) (Math.random() * (len + 1))];
        for (int i = 0; i != charArr.length; i++) {
            charArr[i] = (char) ((int) (Math.random() * range) + 'A');
        }
        return String.valueOf(charArr);
    }

    public static void main(String[] args) {
        int maxLen = 10;
        int testTimes = 50;
        String str = null;
        for (int i = 0; i != testTimes; i++) {
            str = getRandomStringOnlyAToD(maxLen);
            System.out.print("\"" + str + "\"" + " : ");
            System.out.print(minCutytc(str)+" ");
            System.out.println(minCut(str));
        }
    }
}
